{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Permutation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #greedy #array #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #贪心 #数组 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findPermutation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #寻找排列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>由范围 <code>[1,n]</code> 内所有整数组成的 <code>n</code> 个整数的排列&nbsp;<code>perm</code>&nbsp;可以表示为长度为 <code>n - 1</code> 的字符串 <code>s</code> ，其中:</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果 <code>perm[i] &lt; perm[i + 1]</code> ，那么 <code>s[i] == 'I'</code></li>\n",
    "\t<li>如果&nbsp;<code>perm[i] &gt; perm[i + 1]</code>&nbsp;，那么 <code>s[i] == 'D'</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给定一个字符串 <code>s</code> ，重构字典序上最小的排列&nbsp;<code>perm</code>&nbsp;并返回它。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong> s = \"I\"\n",
    "<strong>输出：</strong> [1,2]\n",
    "<strong>解释：</strong> [1,2] 是唯一合法的可以生成秘密签名 \"I\" 的特定串，数字 1 和 2 构成递增关系。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong> s = \"DI\"\n",
    "<strong>输出：</strong> [2,1,3]\n",
    "<strong>解释：</strong> [2,1,3] 和 [3,1,2] 可以生成秘密签名 \"DI\"，\n",
    "但是由于我们要找字典序最小的排列，因此你需要输出 [2,1,3]。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s[i]</code>&nbsp;只会包含字符 <code>'D'</code> 和 <code>'I'</code>。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-permutation](https://leetcode.cn/problems/find-permutation/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-permutation](https://leetcode.cn/problems/find-permutation/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"I\"', '\"DI\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        if not s: return [1]\n",
    "        res, asc = [1], 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i:i+1] == 'D':\n",
    "                res.insert(asc,i+2)\n",
    "            else:\n",
    "                res.append(i+2)\n",
    "                asc = i+ 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        res = [1]\n",
    "        last = -1\n",
    "        for i, c in enumerate(s):\n",
    "            if c == 'I':\n",
    "                res.append(i + 2)\n",
    "                last = i\n",
    "                continue\n",
    "            else:\n",
    "                res.insert(last + 1, i + 2)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        if not s: return [1]\n",
    "        res, asc = [1], 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i:i+1] == 'D':\n",
    "                res.insert(asc, i + 2)\n",
    "            else:\n",
    "                res.append(i + 2)\n",
    "                asc = i + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        if not s:\n",
    "            return [1]\n",
    "        res,asc = [1],0\n",
    "        for i in range(len(s)):\n",
    "            if s[i:i+1] =='D':\n",
    "                res.insert(asc,i+2)\n",
    "            else:\n",
    "                res.append(i+2)\n",
    "                asc = i + 1\n",
    "        return res\n",
    "        # if not s:\n",
    "        #     return [1]\n",
    "        # res,asc = [1],0\n",
    "        # for i in range(len(s)):\n",
    "        #     if s[i:i+1] == 'D':\n",
    "        #         res.insert(asc,i+2)\n",
    "        #     else:\n",
    "        #         res.append(i+2)\n",
    "        #         asc = i + 1\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        if not s:\n",
    "            return [1]\n",
    "        res, asc = [1], 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == 'D':\n",
    "                res.insert(asc, i + 2)\n",
    "            else:\n",
    "                res.append(i + 2)\n",
    "                asc = i + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        if not s:\n",
    "            return [1]\n",
    "\n",
    "        res=[1]\n",
    "        idx=0\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            if s[i]=='D':\n",
    "                res.insert(idx,i+2)\n",
    "            else:\n",
    "                res.append(i+2)\n",
    "                idx=i+1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        output = list(range(1, len(s)+2))\n",
    "        i = 0\n",
    "        j = 1\n",
    "        while j < len(s) + 1:\n",
    "            if s[j-1] == 'I':\n",
    "                if i != j:\n",
    "                    ii = i\n",
    "                    jj = j - 1\n",
    "                    while ii < jj:\n",
    "                        output[ii], output[jj] = output[jj], output[ii]\n",
    "                        ii += 1\n",
    "                        jj -= 1\n",
    "                i = j\n",
    "                j += 1\n",
    "            else:\n",
    "                j += 1\n",
    "        if s[-1] == 'D':\n",
    "            ii = i\n",
    "            jj = j - 1\n",
    "            while ii < jj:\n",
    "                output[ii], output[jj] = output[jj], output[ii]\n",
    "                ii += 1\n",
    "                jj -= 1\n",
    "        return output\n",
    "        # if s[0] == 'I':\n",
    "        #     output.append(1)\n",
    "        #     output.append(2)\n",
    "        # else:\n",
    "        #     output.append(2)\n",
    "        #     output.append(1)\n",
    "        # i = 3\n",
    "        # for c in s[1:]:\n",
    "        #     output.append(i)\n",
    "        #     if c == 'D':\n",
    "        #         j = i - 2\n",
    "        #         while j >= 0:\n",
    "        #             if s[j] == 'I':\n",
    "        #                 break\n",
    "        #             else:\n",
    "        #                 output[j+1], output[j] = output[j], output[j+1]\n",
    "        #             j -= 1\n",
    "        #     i += 1\n",
    "        # return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        if not s: return [1]\n",
    "        res, asc = [1], 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i:i+1] == 'D':\n",
    "                res.insert(asc, i + 2)\n",
    "            else:\n",
    "                res.append(i + 2)\n",
    "                asc = i + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        i=0\n",
    "        ret=[]\n",
    "        k=1\n",
    "        judge=0\n",
    "        while i<len(s):\n",
    "            left=i\n",
    "            while i<len(s) and s[i]=='D':\n",
    "                i+=1\n",
    "            temp=[]\n",
    "            for j in range(i-left+1):\n",
    "                temp.append(k)\n",
    "                k+=1\n",
    "            temp.reverse()\n",
    "            ret+=temp\n",
    "            i+=1\n",
    "        temp=[]\n",
    "        for i in range(len(s)-i):\n",
    "            temp.append(k)\n",
    "            k+=1\n",
    "        temp.reverse()\n",
    "        ret+=temp\n",
    "        if s[-1]=='I':\n",
    "            ret.append(k)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        if not s:return [1]\n",
    "        res=[1]\n",
    "        asc=0\n",
    "        for i in range(len(s)):\n",
    "            if s[i]=='D':\n",
    "                res.insert(asc,i+2)\n",
    "            else:\n",
    "                res.append(i+2)\n",
    "                asc=i+1 ### 始终记录增长序列停下来的地方的后一个位置\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        if not s: return [1]\n",
    "        res, asc = [1], 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i:i + 1] == 'D':\n",
    "                res.insert(asc, i + 2)\n",
    "            else:\n",
    "                res.append(i + 2)\n",
    "                asc = i + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        res = [1]\n",
    "        n = len(s)\n",
    "        idx = 2\n",
    "        continueD = 0\n",
    "        for rel in s:\n",
    "            # print(res)\n",
    "            if rel == 'I':\n",
    "                continueD = 0\n",
    "                res.append(idx)\n",
    "            else:\n",
    "                continueD += 1\n",
    "                res.insert(idx-1-continueD,idx)\n",
    "            idx += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        n, num = len(s),  1\n",
    "        res, stack = [], []\n",
    "        for i in range(n):\n",
    "            if s[i] == 'D':\n",
    "                stack.append(num)\n",
    "            else:\n",
    "                res.append(num)\n",
    "                while stack:\n",
    "                    res.append(stack.pop())\n",
    "            num += 1\n",
    "        res.append(num)     \n",
    "        while stack:\n",
    "            res.append(stack.pop())\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        if not s:\n",
    "            return [1]\n",
    "        res = [1]\n",
    "        last_index_of_i = -1\n",
    "        for index, ch in enumerate(s):\n",
    "            if ch == 'I':\n",
    "                res.append(index + 2)\n",
    "                last_index_of_i = index\n",
    "                continue\n",
    "            if ch == 'D':\n",
    "                res.insert(last_index_of_i + 1, index + 2)\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        n = len(s) + 1\n",
    "        stack = []\n",
    "        ans = []\n",
    "        for i, c in enumerate(s, 1):\n",
    "            stack.append(i)\n",
    "            if c == 'I':\n",
    "                ans += reversed(stack)\n",
    "                stack.clear()\n",
    "        stack.append(n)\n",
    "        ans += reversed(stack)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        result = [1]\n",
    "\n",
    "        if not s:\n",
    "            return result\n",
    "\n",
    "        flag = 0\n",
    "\n",
    "        for index, char in enumerate(s):\n",
    "            if char == \"D\":\n",
    "                result.insert(flag, index+2)\n",
    "            else:\n",
    "                result.append(index+ 2)\n",
    "                flag = index + 1\n",
    "        return  result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        if not s: return [1]\n",
    "        res, asc = [1], 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i:i+1] == 'D':\n",
    "                res.insert(asc, i + 2)\n",
    "            else:\n",
    "                res.append(i + 2)\n",
    "                asc = i + 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        def reverse(array, left, right):\n",
    "            while left < right:\n",
    "                array[left], array[right] = array[right], array[left]\n",
    "                left += 1\n",
    "                right -= 1\n",
    "\n",
    "        ans = [i for i in range(1, len(s) + 2)]\n",
    "\n",
    "        i = 1\n",
    "        while i <= len(s):\n",
    "            j = i\n",
    "            while i <= len(s) and s[i - 1] == 'D':\n",
    "                i += 1\n",
    "            reverse(ans, j - 1, i - 1)\n",
    "            i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        n = len(s)\n",
    "        res = [_ + 1 for _ in range(n + 1)]\n",
    "        start = False\n",
    "        j = 0\n",
    "        for i in range(n):\n",
    "            if s[i] == 'D' and not start:\n",
    "                start = True\n",
    "                j = i\n",
    "            if s[i] == 'I' and start:\n",
    "                start = False\n",
    "                res[j:i + 1] = res[j:i + 1][::-1]\n",
    "        if start:\n",
    "            res[j:n+1] = res[j:n+1][::-1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        if not s:\n",
    "            return [1]\n",
    "        res,asc = [1],0\n",
    "        for i in range(len(s)):\n",
    "            if s[i:i+1] == 'D':\n",
    "                res.insert(asc,i+2)\n",
    "            else:\n",
    "                res.append(i+2)\n",
    "                asc = i + 1\n",
    "        return res\n",
    "        # if not s: return [1]\n",
    "        # res, asc = [1], 0\n",
    "        # for i in range(len(s)):\n",
    "        #     if s[i:i+1] == 'D':\n",
    "        #         res.insert(asc, i + 2)\n",
    "        #     else:\n",
    "        #         res.append(i + 2)\n",
    "        #         asc = i + 1\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        res = [1]\n",
    "        idx = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == 'D':\n",
    "                res.insert(idx, i+2)\n",
    "            else:\n",
    "                res.append(i+2)\n",
    "                idx = i + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        n = len(s)\n",
    "        if n == 0: return [1]\n",
    "        res, j = [1], 0\n",
    "        for i in range(n):\n",
    "            if s[i] == 'D':\n",
    "                res.insert(j, i + 2)\n",
    "            else:\n",
    "                res.append(i + 2)\n",
    "                j = i + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        def reverse(perm: list, start: int, end: int) -> None:\n",
    "            \"\"\"局部定义的reverse函数，用于反转perm中从start到end的部分。\"\"\"\n",
    "            while start < end:\n",
    "                perm[start], perm[end] = perm[end], perm[start]\n",
    "                start += 1\n",
    "                end -= 1\n",
    "\n",
    "        ls = len(s)\n",
    "        lp = ls + 1\n",
    "        perm = [i for i in range(1, lp + 1)]\n",
    "        i = 1\n",
    "        while i <= ls:\n",
    "            if s[i - 1] == 'D':\n",
    "                j = i\n",
    "                while i <= ls and s[i - 1] == 'D':\n",
    "                    i += 1\n",
    "                reverse(perm, j - 1, i - 1)\n",
    "            i += 1\n",
    "        return perm\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        stack = []\n",
    "        res = []\n",
    "        for i in range(len(s)+1):\n",
    "            # every iteration adds the number to stack\n",
    "            stack.append(i+1)\n",
    "            # if it is the final iteration, or encountered \"increase\", clear everything from stack\n",
    "            if i == len(s) or s[i] == \"I\":\n",
    "                while stack:\n",
    "                    num = stack.pop()\n",
    "                    res.append(num)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        if not s:\n",
    "            return [1]\n",
    "        res = [1]\n",
    "        last_index_of_i = -1\n",
    "        for index, ch in enumerate(s):\n",
    "            if ch == 'I':\n",
    "                res.append(index + 2)\n",
    "                last_index_of_i = index\n",
    "                continue\n",
    "            if ch == 'D':\n",
    "                res.insert(last_index_of_i + 1, index + 2)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        result = [1]\n",
    "        if not s:\n",
    "            return result\n",
    "\n",
    "        flag = 0\n",
    "\n",
    "        for index, char in enumerate(s):\n",
    "            if char == \"D\":\n",
    "                result.insert(flag, index + 2)\n",
    "            else:\n",
    "                result.append(index + 2)\n",
    "                flag = index + 1\n",
    "\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def findPermutation(self, s: str) -> List[int]:\n",
    "#         lis,stack,mark=[],[],True\n",
    "#         sum=0\n",
    "#         for i in range(len(s)+1,0,-1):\n",
    "#             lis.append(i)\n",
    "#         a=lis.pop(-1)\n",
    "#         b=lis.pop(-1)\n",
    "#         for i in s:\n",
    "#             if i=='D':\n",
    "#                 sum+=1\n",
    "#                 temp=[]\n",
    "#                 if mark:\n",
    "#                     stack.append(b)\n",
    "#                     stack.append(a)\n",
    "#                     mark=False\n",
    "#                     continue\n",
    "#                 c=lis.pop(-1)\n",
    "#                 for i in range(sum):\n",
    "#                     a=stack.pop(-1)\n",
    "#                     temp.append(a)\n",
    "#                 stack.append(c)\n",
    "#                 for i in range(sum-1,-1,-1):\n",
    "#                     stack.append(temp[i])\n",
    "#             if i=='I':\n",
    "#                 sum=0\n",
    "#                 if mark:\n",
    "#                     stack.append(a)\n",
    "#                     stack.append(b)\n",
    "#                     mark=False\n",
    "#                     continue\n",
    "#                 c=lis.pop(-1)\n",
    "#                 stack.append(c)        \n",
    "#         return stack\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        stack = []\n",
    "        result = []\n",
    "        n = len(s) + 1\n",
    "        for i in range(1, n+1):\n",
    "            stack.append(i)\n",
    "            if i == n or s[i-1] == 'I':\n",
    "                while stack:\n",
    "                    result.append(stack.pop())\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        n = len(s)\n",
    "        lst = [i for i in range(1, n + 2)]\n",
    "        i, j = 0, 0\n",
    "        while j < n:\n",
    "            while j < n and s[j] != \"D\":\n",
    "                j += 1\n",
    "            if j == n: break\n",
    "            i = j\n",
    "            while j < n and s[j] == \"D\":\n",
    "                j += 1\n",
    "            reverse(lst, i, j)  # j在s中\"D\"的下一位，正好对应lst； i是s中首个\"D\"，对应lst上一位置\n",
    "        return lst\n",
    "\n",
    "def reverse(lst, start, end):\n",
    "    while start < end:\n",
    "        lst[start], lst[end] = lst[end], lst[start]\n",
    "        start += 1\n",
    "        end -= 1\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        output = []\n",
    "        if s[0] == 'I':\n",
    "            output.append(1)\n",
    "            output.append(2)\n",
    "        else:\n",
    "            output.append(2)\n",
    "            output.append(1)\n",
    "        i = 3\n",
    "        for c in s[1:]:\n",
    "            output.append(i)\n",
    "            if c == 'D':\n",
    "                j = i - 2\n",
    "                while j >= 0:\n",
    "                    if s[j] == 'I':\n",
    "                        break\n",
    "                    else:\n",
    "                        output[j+1], output[j] = output[j], output[j+1]\n",
    "                    j -= 1\n",
    "            i += 1\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        ret = []\n",
    "        todo = 1\n",
    "        used = 0\n",
    "        for c in s:\n",
    "            if c == 'D':\n",
    "                todo += 1\n",
    "                continue\n",
    "            for i in range(todo, 0, -1):\n",
    "                ret.append(used + i)\n",
    "            used += todo\n",
    "            todo = 1\n",
    "        for i in range(todo, 0, -1):\n",
    "            ret.append(used + i)\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        ans = []\n",
    "\n",
    "        stack = []\n",
    "\n",
    "        i = 1\n",
    "        while i <= len(s):\n",
    "            if s[i - 1] == 'I':\n",
    "                stack.append(i)\n",
    "                while stack:\n",
    "                    ans.append(stack.pop())\n",
    "            else:\n",
    "                stack.append(i)\n",
    "            i += 1\n",
    "        stack.append(len(s) + 1)\n",
    "        while stack:\n",
    "            ans.append(stack.pop())\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        def r(s, a, b):\n",
    "            for i in range((b-a) // 2):\n",
    "                s[a+i], s[b-i-1] = s[b-i-1], s[a+i]\n",
    "        \n",
    "        res = []\n",
    "        for j in range(len(s)+1):\n",
    "            res.append(j+1)\n",
    "        j = 1\n",
    "        while j <= len(s):\n",
    "            i = j\n",
    "            while j <= len(s) and s[j-1] == 'D':\n",
    "                j += 1\n",
    "            r(res, i-1, j)\n",
    "            j += 1\n",
    "        return res\n",
    "\n",
    "\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        res = [0] * (len(s) + 1)\n",
    "        stack = []\n",
    "        j = 0\n",
    "        for i in range(1, len(s) + 1):\n",
    "            if s[i - 1] == 'I':\n",
    "                stack.append(i)\n",
    "                while stack:\n",
    "                    res[j] = stack.pop()\n",
    "                    j += 1\n",
    "            else:\n",
    "                stack.append(i)\n",
    "        stack.append(len(s) + 1)\n",
    "        while stack:\n",
    "            res[j] = stack.pop()\n",
    "            j += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def findPermutation(self, s: str) -> List[int]:\n",
    "#         lis,stack,mark=[],[],True\n",
    "#         sum=0\n",
    "#         for i in range(len(s)+1,0,-1):\n",
    "#             lis.append(i)\n",
    "#         a=lis.pop(-1)\n",
    "#         b=lis.pop(-1)\n",
    "#         for i in s:\n",
    "#             if i=='D':\n",
    "#                 sum+=1\n",
    "#                 temp=[]\n",
    "#                 if mark:\n",
    "#                     stack.append(b)\n",
    "#                     stack.append(a)\n",
    "#                     mark=False\n",
    "#                     continue\n",
    "#                 c=lis.pop(-1)\n",
    "#                 for i in range(sum):\n",
    "#                     a=stack.pop(-1)\n",
    "#                     temp.append(a)\n",
    "#                 stack.append(c)\n",
    "#                 for i in range(sum-1,-1,-1):\n",
    "#                     stack.append(temp[i])\n",
    "#             if i=='I':\n",
    "#                 sum=0\n",
    "#                 if mark:\n",
    "#                     stack.append(a)\n",
    "#                     stack.append(b)\n",
    "#                     mark=False\n",
    "#                     continue\n",
    "#                 c=lis.pop(-1)\n",
    "#                 stack.append(c)        \n",
    "#         return stack\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        stack = []\n",
    "        result = []\n",
    "        n = len(s) + 1\n",
    "        for i in range(1, n+1):\n",
    "            stack.append(i)\n",
    "            if i == n or s[i-1] == 'I':\n",
    "                while stack:\n",
    "                    result.append(stack.pop())\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        n = len(s)\n",
    "        res = []\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            if s[i]=='D':\n",
    "                stack.append(i+1)\n",
    "            else:\n",
    "                stack.append(i+1)\n",
    "                while(stack):\n",
    "                    res.append(stack.pop())\n",
    "        stack.append(n+1)\n",
    "        while(stack):\n",
    "            res.append(stack.pop())\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        \n",
    "        stack = [1]\n",
    "        ans = []\n",
    "        for e in s:\n",
    "            if e == 'D':\n",
    "                stack.append(stack[-1]+1)\n",
    "            else:\n",
    "                i = stack[-1]+1\n",
    "                while stack:\n",
    "                    ans.append(stack.pop())\n",
    "                stack.append(i)\n",
    "        while stack:\n",
    "            ans.append(stack.pop())\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        lis,stack=[],[]\n",
    "        len_s=len(s)+1\n",
    "        for i in range(1,len_s+1):\n",
    "            stack.append(i)\n",
    "            if  i==len_s or s[i-1]=='I':\n",
    "                while stack:\n",
    "                    lis.append(stack.pop())\n",
    "        return lis\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        n = len(s)\n",
    "        res = [0] * (n + 1)\n",
    "        stack = []\n",
    "        j = 0\n",
    "        for i in range(1, n + 1):\n",
    "            if s[i - 1] == \"I\":\n",
    "                stack.append(i)\n",
    "                while len(stack) > 0:\n",
    "                    res[j] = stack.pop(-1)\n",
    "                    j += 1\n",
    "            else:\n",
    "                stack.append(i)\n",
    "        stack.append(n + 1)\n",
    "        while len(stack) > 0:\n",
    "            res[j] = stack.pop(-1)\n",
    "            j += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        stack, ret = [], []\n",
    "        cur = len(s) + 1\n",
    "        for i in range(len(s) - 1, -1, -1):\n",
    "            stack.append(cur)\n",
    "            cur -= 1\n",
    "            if s[i] == 'I':\n",
    "                ret += stack[::-1]\n",
    "                stack = []\n",
    "        if s[0] == 'D':\n",
    "            stack.append(cur)\n",
    "            ret += stack[::-1]\n",
    "        else:\n",
    "            ret += [cur]\n",
    "        ans = ret[::-1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def findPermutation(self, s: str) -> List[int]:\n",
    "#         lis,stack,mark=[],[],True\n",
    "#         sum=0\n",
    "#         for i in range(len(s)+1,0,-1):\n",
    "#             lis.append(i)\n",
    "#         a=lis.pop(-1)\n",
    "#         b=lis.pop(-1)\n",
    "#         for i in s:\n",
    "#             if i=='D':\n",
    "#                 sum+=1\n",
    "#                 temp=[]\n",
    "#                 if mark:\n",
    "#                     stack.append(b)\n",
    "#                     stack.append(a)\n",
    "#                     mark=False\n",
    "#                     continue\n",
    "#                 c=lis.pop(-1)\n",
    "#                 for i in range(sum):\n",
    "#                     a=stack.pop(-1)\n",
    "#                     temp.append(a)\n",
    "#                 stack.append(c)\n",
    "#                 for i in range(sum-1,-1,-1):\n",
    "#                     stack.append(temp[i])\n",
    "#             if i=='I':\n",
    "#                 sum=0\n",
    "#                 if mark:\n",
    "#                     stack.append(a)\n",
    "#                     stack.append(b)\n",
    "#                     mark=False\n",
    "#                     continue\n",
    "#                 c=lis.pop(-1)\n",
    "#                 stack.append(c)        \n",
    "#         return stack\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        stack = []\n",
    "        result = []\n",
    "        n = len(s) + 1\n",
    "        for i in range(1, n+1):\n",
    "            stack.append(i)\n",
    "            if i == n or s[i-1] == 'I':\n",
    "                while stack:\n",
    "                    result.append(stack.pop())\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def findPermutation(self, s: str) -> List[int]:\n",
    "#         lis,stack,mark=[],[],True\n",
    "#         sum=0\n",
    "#         for i in range(len(s)+1,0,-1):\n",
    "#             lis.append(i)\n",
    "#         a=lis.pop(-1)\n",
    "#         b=lis.pop(-1)\n",
    "#         for i in s:\n",
    "#             if i=='D':\n",
    "#                 sum+=1\n",
    "#                 temp=[]\n",
    "#                 if mark:\n",
    "#                     stack.append(b)\n",
    "#                     stack.append(a)\n",
    "#                     mark=False\n",
    "#                     continue\n",
    "#                 c=lis.pop(-1)\n",
    "#                 for i in range(sum):\n",
    "#                     a=stack.pop(-1)\n",
    "#                     temp.append(a)\n",
    "#                 stack.append(c)\n",
    "#                 for i in range(sum-1,-1,-1):\n",
    "#                     stack.append(temp[i])\n",
    "#             if i=='I':\n",
    "#                 sum=0\n",
    "#                 if mark:\n",
    "#                     stack.append(a)\n",
    "#                     stack.append(b)\n",
    "#                     mark=False\n",
    "#                     continue\n",
    "#                 c=lis.pop(-1)\n",
    "#                 stack.append(c)        \n",
    "#         return stack\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        stack = []\n",
    "        result = []\n",
    "        n = len(s) + 1\n",
    "        for i in range(1, n+1):\n",
    "            stack.append(i)\n",
    "            if i == n or s[i-1] == 'I':\n",
    "                while stack:\n",
    "                    result.append(stack.pop())\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        ans = []\n",
    "        stack = []\n",
    "\n",
    "        for i, c in enumerate(s):\n",
    "            stack.append(i + 1)\n",
    "\n",
    "            if c == 'I':\n",
    "                while stack:\n",
    "                    ans.append(stack.pop())\n",
    "                \n",
    "        stack.append(len(s) + 1)\n",
    "\n",
    "        while stack:\n",
    "            ans.append(stack.pop())\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "# # Initialization:\n",
    "# ans = []\n",
    "# stack = []\n",
    "\n",
    "# Traversing the String:\n",
    "\n",
    "# i=0, c='I':\n",
    "\n",
    "# Push 1 onto stack: stack = [1]\n",
    "# Since c='I', pop everything from stack and add to ans: ans = [1], stack = []\n",
    "# i=1, c='D':\n",
    "\n",
    "# Push 2 onto stack: stack = [2]\n",
    "# Don't pop anything because c='D\n",
    "# i=2, c='I':\n",
    "\n",
    "# Push 3 onto stack: stack = [2, 3]\n",
    "# Since c='I', pop everything from stack and add to ans: ans = [1, 3, 2], stack = []\n",
    "# i=3, c='D':\n",
    "\n",
    "# Push 4 onto stack: stack = [4]\n",
    "# Don't pop anything because c='D\n",
    "# i=4, c='D':\n",
    "\n",
    "# Push 5 onto stack: stack = [4, 5]\n",
    "# Don't pop anything because c='D\n",
    "# i=5, c='I':\n",
    "\n",
    "# Push 6 onto stack: stack = [4, 5, 6]\n",
    "# Since c='I', pop everything from stack and add to ans: ans = [1, 3, 2, 6, 5, 4], stack = []\n",
    "# Post-Processing:\n",
    "\n",
    "# After the loop, we push len(s) + 1 = 7 onto the stack: stack = [7]\n",
    "# Then, pop everything from the stack and add to ans: ans = [1, 3, 2, 6, 5, 4, 7]\n",
    "\n",
    "# Thus, the final permutation for the string s = \"IDIDDI\" is [1, 3, 2, 6, 5, 4, 7].\n",
    "\n",
    "# Explanation:\n",
    "\n",
    "# The string starts with an 'I', indicating that the first two numbers in the permutation are in increasing order, so the smallest possible numbers are chosen: 1, 2. However, the next character is 'D', indicating a decrease. Since 2 was already \"used\", the next two numbers in decreasing order that can be chosen are 3, 2. The next two characters are 'I' then 'D', so the smallest possible increasing then decreasing numbers are 4, 5, 4. The string ends with 'I', so the next two numbers in increasing order are 5, 6.\n",
    "\n",
    "# Hence, the permutation is [1, 3, 2, 6, 5, 4, 7].\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        stack = []\n",
    "        ans = []\n",
    "        for i,x in enumerate(s):\n",
    "            stack.append(i + 1)\n",
    "            if x == 'I':\n",
    "                ans += stack[::-1]\n",
    "                stack.clear()\n",
    "        stack.append(len(s) + 1)\n",
    "        return ans + stack[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        from collections import deque\n",
    "        stack = deque()\n",
    "        ans = []\n",
    "        for i, ch in enumerate(s):\n",
    "            stack.append(i + 1)\n",
    "            if ch == 'I':\n",
    "                while stack:\n",
    "                    k = stack.pop()\n",
    "                    ans.append(k)\n",
    "        stack.append(len(s) + 1)\n",
    "        while stack:\n",
    "            k = stack.pop()\n",
    "            ans.append(k)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        n = len(s)+1\n",
    "        s += 'I'\n",
    "\n",
    "        stack = []\n",
    "        result = []\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == 'D':\n",
    "                stack.append(i+1)\n",
    "            else:\n",
    "                result.append(i+1)\n",
    "                while len(stack)>0:\n",
    "                    result.append(stack.pop())\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        n = len(s) + 1\n",
    "        s = '#' + s + '#'\n",
    "        start = 0\n",
    "        rec = []\n",
    "        for i in range(1, n + 1):\n",
    "            if s[i] != s[i - 1]:\n",
    "                rec.append(i - start)\n",
    "                start = i\n",
    "        ans = []\n",
    "        start = 1\n",
    "        rec = rec[1:]\n",
    "        if s[1] == 'D':\n",
    "            a = rec[0]\n",
    "            rec = rec[1:]\n",
    "            ans = list(range(1, a + 2))[::-1]\n",
    "            start = a + 2\n",
    "        else:\n",
    "            ans = [1]\n",
    "            start = 2\n",
    "        if len(rec) % 2:\n",
    "            rec = rec + [0]\n",
    "        m = len(rec)\n",
    "        for i in range(0, m, 2):\n",
    "            ii, dd = rec[i], rec[i + 1]\n",
    "            tmp = []\n",
    "            for j in range(start, ii + start - 1):\n",
    "                tmp.append(j)\n",
    "            tmp.append(start + ii + dd - 1)\n",
    "            for j in range(start + ii + dd - 2, start + ii - 2, -1):\n",
    "                tmp.append(j)\n",
    "            ans.extend(tmp)\n",
    "            start = start + ii + dd\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        n = len(s)\n",
    "        res = [_ + 1 for _ in range(n + 1)]\n",
    "        i = -1\n",
    "        start = False\n",
    "        for j in range(n):\n",
    "            if not start and s[j] == 'D':\n",
    "                start = True\n",
    "                i = j\n",
    "            if start and s[j] == 'I':\n",
    "                start = False\n",
    "                res[i: j + 1] = res[i: j + 1][::-1]\n",
    "        if start:\n",
    "            res[i: n + 1] = res[i: n + 1][::-1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        ret = []\n",
    "        todo = 1\n",
    "        used = 0\n",
    "        s += 'I'\n",
    "        for c in s:\n",
    "            if c == 'D':\n",
    "                todo += 1\n",
    "                continue\n",
    "            for i in range(todo, 0, -1):\n",
    "                ret.append(used + i)\n",
    "            used += todo\n",
    "            todo = 1\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        def reverse(perm: list, start: int, end: int) -> None:\n",
    "            \"\"\"局部定义的reverse函数，用于反转perm中从start到end的部分。\"\"\"\n",
    "            while start < end:\n",
    "                perm[start], perm[end] = perm[end], perm[start]\n",
    "                start += 1\n",
    "                end -= 1\n",
    "\n",
    "        ls = len(s)\n",
    "        lp = ls + 1\n",
    "        perm = [i for i in range(1, lp + 1)]\n",
    "        i = 0\n",
    "        while i < ls:\n",
    "            if s[i] == 'D':\n",
    "                j = i\n",
    "                while i < ls and s[i] == 'D':\n",
    "                    i += 1\n",
    "                reverse(perm, j, i)\n",
    "            i += 1\n",
    "        return perm\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        res, x = [], 1\n",
    "        for sub in s.split('I'):\n",
    "            res.extend(range(x+len(sub), x-1, -1))\n",
    "            x += len(sub)+1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        res, x = [], 1\n",
    "\n",
    "        for sub in s.split('I'):\n",
    "            res.extend(range(x + len(sub), x - 1, -1))\n",
    "            x += len(sub) + 1\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        if not s:\n",
    "            return []\n",
    "        stack = [1]\n",
    "        res = []\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == \"D\":\n",
    "                stack.append(i + 2)\n",
    "            else:\n",
    "                while stack:\n",
    "                    res.append(stack.pop())\n",
    "                stack.append(i + 2)\n",
    "        while stack:\n",
    "            res.append(stack.pop())\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def findPermutation(self, s: str) -> List[int]:\n",
    "#         lis,stack,mark=[],[],True\n",
    "#         sum=0\n",
    "#         for i in range(len(s)+1,0,-1):\n",
    "#             lis.append(i)\n",
    "#         a=lis.pop(-1)\n",
    "#         b=lis.pop(-1)\n",
    "#         for i in s:\n",
    "#             if i=='D':\n",
    "#                 sum+=1\n",
    "#                 temp=[]\n",
    "#                 if mark:\n",
    "#                     stack.append(b)\n",
    "#                     stack.append(a)\n",
    "#                     mark=False\n",
    "#                     continue\n",
    "#                 c=lis.pop(-1)\n",
    "#                 for i in range(sum):\n",
    "#                     a=stack.pop(-1)\n",
    "#                     temp.append(a)\n",
    "#                 stack.append(c)\n",
    "#                 for i in range(sum-1,-1,-1):\n",
    "#                     stack.append(temp[i])\n",
    "#             if i=='I':\n",
    "#                 sum=0\n",
    "#                 if mark:\n",
    "#                     stack.append(a)\n",
    "#                     stack.append(b)\n",
    "#                     mark=False\n",
    "#                     continue\n",
    "#                 c=lis.pop(-1)\n",
    "#                 stack.append(c)        \n",
    "#         return stack\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        stack = []\n",
    "        result = []\n",
    "        n = len(s) + 1\n",
    "        for i in range(1, n+1):\n",
    "            stack.append(i)\n",
    "            if i == n or s[i-1] == 'I':\n",
    "                while stack:\n",
    "                    result.append(stack.pop())\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        ls = len(s)\n",
    "        lp = ls + 1\n",
    "        perm = []\n",
    "        tmp = []\n",
    "        for i in range(1, lp):\n",
    "            if s[i - 1] == 'I':\n",
    "                tmp.append(i)\n",
    "                while tmp:\n",
    "                    perm.append(tmp.pop())\n",
    "            else:\n",
    "                tmp.append(i)\n",
    "        tmp.append(lp)\n",
    "        while tmp:\n",
    "            perm.append(tmp.pop())\n",
    "        return perm\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        res = []\n",
    "        stack = []\n",
    "        if not s: return s\n",
    "        for i in range(len(s)):\n",
    "            stack.append(i+1)\n",
    "            if s[i] == 'I' :\n",
    "                while stack:\n",
    "                    res.append(stack.pop())\n",
    "        stack.append(i+2)\n",
    "        while stack:\n",
    "            res.append(stack.pop())\n",
    "        return res\n",
    "\n",
    "\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        n = len(s) + 1\n",
    "        stack = []\n",
    "        ans = []\n",
    "        for i, c in enumerate(s, 1):\n",
    "            stack.append(i)\n",
    "            if c == 'I':\n",
    "                ans += reversed(stack)\n",
    "                stack.clear()\n",
    "        stack.append(n)\n",
    "        ans += reversed(stack)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "       #感觉这个题直接贪心就行,反转连续为D的子数组即可吧\n",
    "        n=len(s)\n",
    "        s=s+\"#\"\n",
    "        res=list(range(1,n+2))\n",
    "        cnt=0\n",
    "        for i in range(n+1):\n",
    "            if s[i]==\"D\":\n",
    "                cnt+=1\n",
    "            else:\n",
    "                cur=res[i-cnt:i+1]\n",
    "                res[i-cnt:i+1]=cur[::-1]\n",
    "                cnt=0\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        n = len(s)\n",
    "        result, i = [*range(1, n+2)], 0\n",
    "        while i < n:\n",
    "            j = i\n",
    "            while i < n and s[i] == 'D':\n",
    "                i += 1\n",
    "            if i > j:\n",
    "                result[j:i+1] = result[j:i+1][::-1]\n",
    "            else:\n",
    "                i += 1\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        # 贪心，先假设答案为[1...n]，其对应的字符串为[I...I]\n",
    "        # 然后遍历原字符串，碰到D就将D所在的连续区间反转，即可得到字典序最小的答案\n",
    "        ans = list(range(1, len(s)+2))\n",
    "        p = 0\n",
    "        while p < len(s):\n",
    "            if s[p] == 'D':\n",
    "                q = p\n",
    "                while q < len(s) and s[q] == 'D':\n",
    "                    q += 1\n",
    "                # reverse\n",
    "                ans[p:q+1] = ans[p:q+1][::-1]\n",
    "                p = q-1\n",
    "            p += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        stack = []\n",
    "        anw = [0] * (len(s) + 1)\n",
    "        cur_pos = 0\n",
    "        for i in range(1, len(s)+1):\n",
    "            if s[i-1] == \"I\":\n",
    "                stack.append(i)\n",
    "                while stack:\n",
    "                    anw[cur_pos] = stack.pop()\n",
    "                    cur_pos += 1\n",
    "            else:\n",
    "                stack.append(i)\n",
    "        \n",
    "        stack.append(len(s)+1)\n",
    "        while stack:\n",
    "            anw[cur_pos] = stack.pop()\n",
    "            cur_pos += 1\n",
    "        \n",
    "        return anw"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        length = len(s)\n",
    "        perm = list(range(1, len(s)+2))\n",
    "        self.ret = []\n",
    "        stack = []\n",
    "        for i in range(length):\n",
    "            if s[i] == 'D':\n",
    "                stack.append(perm[i])\n",
    "            if s[i] == 'I':\n",
    "                stack.append(perm[i])\n",
    "                while stack:\n",
    "                    self.ret.append(stack.pop())\n",
    "        stack.append(perm[-1])\n",
    "        while stack:\n",
    "            self.ret.append(stack.pop())\n",
    "        return self.ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        res, x = [], 1\n",
    "        for sub in s.split('I'):\n",
    "            res.extend(range(x+len(sub), x-1, -1))\n",
    "            x += len(sub)+1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPermutation(self, s: str) -> List[int]:\n",
    "        #感觉这个题直接贪心就行,反转连续为D的子数组即可吧\n",
    "        n=len(s)\n",
    "        #哨兵节点\n",
    "        s=s+\"#\"\n",
    "        res=list(range(1,n+2))\n",
    "        cnt=0\n",
    "        for i in range(n+1):\n",
    "            if s[i]==\"D\":\n",
    "                cnt+=1\n",
    "            else:\n",
    "                cur=res[i-cnt:i+1]\n",
    "                res[i-cnt:i+1]=cur[::-1]\n",
    "                cnt=0\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
